/*
 * @lc app=leetcode.cn id=977 lang=cpp
 *
 * [977] 有序数组的平方
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    vector<int> sortedSquares(vector<int> &nums)
    {
        vector<int> ans(nums.size());
        //找到第一个>=0的位置
        int pos = std::find_if(nums.begin(), nums.end(), [](const int i)
                               { return i >= 0; }) -
                  nums.begin();

        int neg_pos = pos - 1;
        int ans_pos = 0;
        while (neg_pos >= 0 && pos < nums.size())
        {
            if (-nums[neg_pos] > nums[pos])
            {
                ans[ans_pos++] = nums[pos] * nums[pos];
                pos++;
            }
            else
            {
                ans[ans_pos++] = nums[neg_pos] * nums[neg_pos];
                neg_pos--;
            }
        }
        while (neg_pos >= 0)
        {
            ans[ans_pos++] = nums[neg_pos] * nums[neg_pos];
            neg_pos--;
        }
        while (pos < nums.size())
        {
            ans[ans_pos++] = nums[pos] * nums[pos];
            pos++;
        }
        return ans;
    }
};
// @lc code=end
